#include "secret_divide.h"
#include <stdlib.h>
#include <cstdlib>
#include <QtCore>
#include <QString>
#include <QDebug>

secret_divide::secret_divide()
{

}

void secret_divide::divide(int secret, int n, int k, int *result, QString &eq)
{
    int ai[k-1];
    int p;
    int ki[n];

    //заполним массив коэффициентов ai случайными числами
    //srand(1000);
    for (int i=0;i<k-1;i++) ai[i]=qrand();

    for (int i=0;i<k-1;i++) qDebug() << QString::number(ai[i]);

    //Выберем простое число p>secret
    p=secret;
    while (p<=secret) p = qrand();
    //p = secret+1;
    while (!isSimple(p)) p++;

    //сформируем массив координат n точек
    for (int i=0;i<n;i++) ki[i]=0;
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<k-1;j++) ki[i]=ki[i]+ai[j]*qPow(i+1,j+1);
        ki[i]=(ki[i]+secret)%p;
    }

    //запись результата
    result[0]=k-1;
    result[1]=p;
    for (int i=2;i<n+2;i++) result[i]=ki[i-2];

    eq = "F(X) = ";
    for (int i=k-2;i>=0;i--) eq = eq + QString::number(ai[i])+"*X^"+QString::number(i+1)+" + ";
    eq = eq + QString::number(secret)+ " mod " + QString::number(p);
}

int secret_divide::restore(int pow, int p, int *x, int *y)
{

    //x - части секретов
    //y - номера участников
    int a[pow+1];
    int li[pow+1];
    for (int i=0;i<pow+1;i++) a[i]=0;

    for (int i=0;i<pow+1;i++)
    {
        //qDebug() << "i=" << QString::number(i);
        l_i(pow,p,i,y,li);              //вычисляем коэффициенты li
        for (int j=0;j<pow+1;j++) a[j]+=li[j]*x[i];
    }

    for (int i=0;i<pow+1;i++) a[i]%=p;

    //for (int i=0;i<pow+1;i++) qDebug() << QString::number(a[i]);
    return a[0];
}

bool secret_divide::isSimple(int n)
{
    if(n == 1 || n<=0)
        return false;
    for(int i=2; i<=n/2; ++i)
       if(n%i == 0)
           return false;
    return true;
}

void secret_divide::l_i(int pow, int p, int i, int *y, int *result)
{
    //скопируем
    int x[pow+1];
    for (int k=0;k<pow+1;k++) x[k]=y[k];

    //сдвинем массив x вправо начиная с i-го элемента
    int X = x[i];
    for (int j=i;j<pow;j++) x[j]=x[j+1];

    //вычислим знаменатель l(i)
    int z = 1;
    for (int j=0;j<pow;j++) z = z*(X-x[j]);
    while (z<0) z+=p;
    if (z>=p) z%=p;

    //вычислим коэффициенты числителя
    int c[pow+1];
    int tmp[pow+1];
    for (int k=0;k<=pow;k++) c[k]=0;
    c[1] = 1;
    c[0]=-1*x[0];
    for (int j=1;j<pow;j++)
    {
        for (int k=0;k<=pow;k++) tmp[k] = 0;         //обнуляем tmp
        for (int k=0;k<=pow;k++) tmp[k+1] = c[k];    //переписываем массив С в tmp со сдвигом!

        for (int k=0;k<=pow;k++) tmp[k] = tmp[k]+ (c[k]*-1*x[j]); //получили новый tmp!
        for (int k=0;k<=pow;k++) c[k] = tmp[k];      //перепишем обратно в С
    }

    //по модулю P
    for (int k=0;k<pow+1;k++)
    {
        while (c[k]<0) c[k]=c[k]+p;
        if (c[k]>=p) c[k]=c[k]%p;
    }

    //найдем новый знаменатель
    int z1 = 1;
    while ((z*z1)%p!=1) z1++;

    //умножим на него коэффициенты
    for (int k=0;k<pow+1;k++) c[k]=(c[k]*z1)%p;

    for (int k=0;k<pow+1;k++) result[k]=c[k];
}
